package dynamic;

public class MinJumps
{

  /*
   * Given an array of integers where each element represents the max number of
   * steps that can be made forward from that element.
   * Write a function to return the minimum number of jumps to reach the end of
   * the array (starting from the first element).
   * If an element is 0, then cannot move through that element.
   * Example:
   * I nput: arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
   * Output: 3 (1-> 3 -> 8 ->9)
   */
  public static int minJumps(int[] array)
  {
    int n = array.length;
    int[] jumps = new int[n];
    if (n == 0 || array[0] == 0) return Integer.MAX_VALUE;
    jumps[0] = 0;
    for (int i = 1 ; i < n ; i++) {
      jumps[i] = Integer.MAX_VALUE;
      for (int j = 0 ; j < i ; j++) {
        if (i <= j + array[j] && jumps[j] != Integer.MAX_VALUE) {
          jumps[i] = jumps[j] + 1;
          break;
        }
      }
    }

    return jumps[n - 1];
  }

  public static void main(String[] args)
  {
    // TODO Auto-generated method stub
    int[] array = { 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 };
    System.out.println(minJumps(array));
  }

}
